package com.atwulidun.sort;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
        shellSortII(arr);
//        shellSortII(arr);
        System.out.println(Arrays.toString(arr));
    }

    //    // 希尔排序(交换法)
//    public static void shellSortI(int[] arr) {
//        int count = 0;
//        // 第一个for循环控制轮数
//        for (int i = arr.length / 2; i > 0; i /= 2) {
//            // 第二个循环用来确定某一组当前无序列表的第一个元素(注意：每一组所进行的插入排序是交替进行的)
//            // 这里的j是从第一组的第二个数开始
//            for (int j = i; j < arr.length; j++) {
//                // 第三个循环：将第二个循环中确定的该组当前无序列表的第一个元素和前面有序列表的元素依次从后往前比较，进行插入排序
//                // 注意：步长为i，即当前轮的组数
//                // 这里的k = j - i是从当前组当前该元素的前一个元素开始
//                for (int k = j - i; k >= 0; k -= i) {
//                    if (arr[k] > arr[k + i]) {
//                        int temp = arr[k];
//                        arr[k] = arr[k + i];
//                        arr[k + i] = temp;
//                    }
//                }
//            }
//            System.out.println("第" + ++count + "轮排序：");
//            System.out.println(Arrays.toString(arr));
//        }
//        System.out.println("全部排序完后为：");
//        System.out.println(Arrays.toString(arr));
//    }
//
//    // 希尔排序(移位法，此法效率更高)
//    public static void shellSortII(int[] arr) {
//        int count = 0;
//        for (int i = arr.length / 2; i > 0; i /= 2) {
//            for (int j = i; j < arr.length; j++) {
//                int insertValue = arr[j];// 注意：这里不小心写成arr[i]了，运行出错！！！！！！！！！
//                int insertIndex = j - i;
//                while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
//                    arr[insertIndex + i] = arr[insertIndex];
//                    insertIndex -= i;
//                }
//                if ((insertIndex + i) != j) {
//                    arr[insertIndex + i] = insertValue;
//                }
//            }
//            System.out.println("第" + ++count + "轮排序：");
//            System.out.println(Arrays.toString(arr));
//        }
//        System.out.println("全部排序完后为：");
//        System.out.println(Arrays.toString(arr));
//    }
    private static void shellSortI(int[] arr) {
        for (int i = arr.length / 2; i > 0; i /= 2) {
            for (int j = i; j < arr.length; j++) {
                int insertVal = arr[j];
                int insertIdx = j - i;
                for (int k = j - i; k >= 0; k -= i) {
                    if (arr[k + i] < arr[k]) {
                        int temp = arr[k + i];
                        arr[k + i] = arr[k];
                        arr[k] = temp;
                    }
                }
            }
        }
    }

    private static void shellSortII(int[] arr) {
        for (int i = arr.length / 2; i > 0; i /= 2) {
            for (int j = i; j < arr.length; j++) {
                int insertVal = arr[j];
                int insertIdx = j - i;
                while (insertIdx >= 0 && insertVal < arr[insertIdx]) {
                    arr[insertIdx + i] = arr[insertIdx];
                    insertIdx -= i;
                }
                if (insertIdx + i != j) {
                    arr[insertIdx + i] = insertVal;
                }
            }
        }
    }
}
